package main

func findTargetSumWays(nums []int, S int) int {
	if len(nums) == 0 {
		return 0
	}
	sum := 0
	for _, n := range nums {
		sum += n
	}
	if sum < S || (S+sum)%2 == 1 {
		return 0
	}
	p := (S + sum) >> 1
	dp := make([]int, len(nums)+1000)
	dp[0] = 1
	for _, n := range nums {
		for i := p; i >= n; i-- {
			dp[i] += dp[i-n]
		}
	}
	return dp[p]
}

func main() {
	findTargetSumWays([]int{1000}, 1000)
}
